今天我們要來看的是 Binary Search Tree (BSTs)。Tree 是由有限節點組成具有層次關係的集合。以下圖為例，最上面的節點稱作根節點 (Root)，也就是沒有父節點 (Parent)。而每個節點會有零個以上的子節點 (Children)。每個節點都只能有一個父節點 (除了根節點)。在一棵樹裡面是沒有 Cycle 的，也就是你不會在一棵樹裡頭看到環。由於這不是專門介紹資料結構的文章，所以更多細節請參考這裡。

From Wiki

那麼 Binary Search Tree，也就是二元搜尋樹又是什麼呢？所謂二元是指一個節點最多只有兩個子節點。從下圖可以看到一個二元搜尋樹之中，一個節點的左子節點 (或整個左子節點所包含的子樹) 的值，一定都小於節點的值，而右子節點 (或整個右子節點所包含的子樹)的值，一定都大於節點的值。所以一個二元搜尋樹內的節點是有順序關係的，所以用在搜尋、排序等等情境，或進而被用來發展其他資料結構。更詳細的細節可以參考這裡。

From Wiki

那麼接下來就讓我們看看這四個語言要怎麼實作 BST 吧！GoGo!

Python 3

class Node:
    def __init__(self, data):
        self.right = None
        self.left = None
        self.data = data

def insert(root, data):
    if root is None:
        return Node(data)
    else:
        if data <= root.data:
          cur = insert(root.left, data)
          root.left = cur
        else:
          cur = insert(root.right, data)
          root.right = cur
        return root

def get_height(root):
    return -1 if root is None else 1 + max(get_height(root.left), get_height(root.right))

root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 10)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 14)
root = insert(root, 4)
root = insert(root, 7)
root = insert(root, 13)
height = get_height(root)
print(height)

• 跟在建 Linked list 的 Node 有點像，只是在 BST 中的每個 Node 有兩個子節點，所以會有 left 和 right 來分別指到左子節點和右子節點，另外當然也有 data 的部分囉！
• 插入新節點的 Function 是 insert，概念上是從 root 開始，假使一開始連 root 都沒有就直接生成一個新的 Node (Node(data))。如果輸入的值小於等於 root 的值就以遞迴的方式，呼叫 insert 但此時給的是左子樹的 Node 來視為這個 insert 的 root。完成之後記得將 root 的左子樹設成剛才遞迴得到的左子樹的根 (root.left = cur)。假設輸入的值大於 root 的值，一樣也是用遞迴的方式，只是這時候 insert 的是右子樹囉！
• 另外 get_height 這個 Function 是告訴我們這個 BST 的樹有多高，也就是最深的子樹有幾個 Edge 高，以上面第二個圖為例，就是 3。概念上是從 root 出發，看左子樹和右子樹誰比較高。為了能夠有遞迴的效果，我們讓即使只有一個節點也有高度 1，但是只要左右子節點是 None 的話，就要 -1 扣回來囉！